package com.tgy.leetcode;

import java.util.Arrays;
import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 2021/3/6 下午8:56
 *
 * https://leetcode-cn.com/problems/next-greater-element-ii/
 */
public class _503_下一个更大元素_II {

    public static int[] nextGreaterElements(int[] nums) {

        int len = nums.length;
        int[] res = new int[len];

        if (len == 0) {

            return res;
        }

        for (int i = 0; i < res.length; i++) {
            res[i] = -1;
        }

        Stack<Integer> stack = new Stack<>();
        int index = 0;
        int dLen = (len << 1);
        while (index < dLen ) {


            int realIndex = index >= len ? index - len:index;

            while (!stack.isEmpty() && nums[stack.peek()] < nums[realIndex]) {

                res[stack.pop()] = nums[realIndex];
            }
            stack.push(realIndex);
            index++;
        }
        return res;
    }

    public static void main(String[] args) {

//        int[] nums = {1,2,3,4,3};
        int[] nums = {5,4,3,2,1};
        int[] res = nextGreaterElements(nums);

        System.out.println(Arrays.toString(res));

    }
}
